package list

import "my-godis/lib/utils"

type node struct {
	val  interface{}
	prev *node
	next *node
}

// LinkedList is doubly linked list
type LinkedList struct {
	first *node
	last  *node
	size  int
}

func Make(vals ...interface{}) *LinkedList {
	list := &LinkedList{}
	for _, v := range vals {
		list.Add(v)
	}
	return list
}

// Add adds value to the tail
func (list *LinkedList) Add(val interface{}) {
	if list == nil {
		panic("list is  nil")
	}
	n := &node{val: val}
	if list.last == nil {
		// empty list
		list.first = n
		list.last = n
	} else {
		n.prev = list.last
		list.last.next = n
		list.last = n
	}
	list.size++
}

// find the node by given index
func (list *LinkedList) find(index int) (n *node) {
	// 小于就从头开始找 否则从尾开始找
	if index < list.size/2 {
		n = list.first
		for i := 0; i < index; i++ {
			n = n.next
		}
	} else {
		n = list.last
		for i := list.size - 1; i > index; i-- {
			n = n.prev
		}
	}
	return n
}

// Get returns value at the given index
func (list *LinkedList) Get(index int) (val interface{}) {
	if list == nil {
		panic("list is nil")
	}
	if index < 0 || index >= list.size {
		panic("index out of bound")
	}
	return list.find(index).val
}

// Set updates value at the given index, the index should between [0, list.size]
func (list *LinkedList) Set(index int, val interface{}) {
	if list == nil {
		panic("list is nil")
	}
	if index < 0 || index >= list.size {
		panic("index out of bound")
	}
	n := list.find(index)
	n.val = val
}

// Insert inserts value at the given index, the original element at the given index will move backward
func (list *LinkedList) Insert(index int, val interface{}) {
	if list == nil {
		panic("list is nil")
	}
	if index < 0 || index > list.size {
		panic("index out of bound")
	}
	if index == list.size {
		list.Add(val)
		return
	}
	// insert in front of pivot
	pivot := list.find(index)
	n := &node{val: val, prev: pivot.prev, next: pivot}
	if pivot.prev == nil {
		list.first = n
	} else {
		pivot.prev.next = n
	}
	pivot.prev = n
	list.size++
}

func (list *LinkedList) removeNode(n *node)  {
	if n.prev == nil {
		list.first = n.next
	}else {
		n.prev.next = n.next
	}
	if n.next == nil {
		list.last = n.prev
	}else {
		n.next.prev = n.prev
	}
	n.prev = nil
	n.next = nil
	list.size--
}

// Remove removes value at the given index
func (list *LinkedList) Remove(index int) (val interface{}) {
	if list == nil {
		panic("list is nil")
	}
	if index < 0 || index >= list.size {
		panic("index out of bound")
	}
	n := list.find(index)
	val = n.val
	list.removeNode(n)
	return val
}

// RemoveLast removes the last element and returns its value
func (list *LinkedList) RemoveLast() (val interface{})  {
	if list == nil {
		panic("list is nil")
	}
	if list.last == nil {
		return nil
	}
	n := list.last
	list.removeNode(n)
	return n.val
}

// RemoveAllByVal removes all elements with the given val
func (list *LinkedList) RemoveAllByVal(val interface{}) int {
	if list == nil {
		panic("list is nil")
	}
	curr := list.first
	removed := 0
	var next *node
	for curr != nil {
		next = curr.next
		if utils.Equals(curr.val, val) {
			list.removeNode(curr)
			removed++
		}
		curr = next
	}
	return removed
}

// RemoveByVal removes at most `count` values of the specified value in this list
// scan from left to right
func (list *LinkedList) RemoveSomeByVal(val interface{}, count int) int {
	if list == nil {
		panic("list is nil")
	}
	curr := list.first
	removed := 0
	var next *node
	for curr != nil {
		next = curr.next
		if utils.Equals(curr.val, val) {
			list.removeNode(curr)
			removed++
		}
		if removed == count {
			break
		}
		curr = next
	}
	return removed
}


// ReverseRemoveByVal removes at most `count` values of the specified value in this list
// scan from right to left
func (list *LinkedList) ReverseRemoveSomeByVal(val interface{}, count int) int {
	if list == nil {
		panic("list is nil")
	}
	curr := list.last
	removed := 0
	var prev *node
	for curr != nil {
		prev = curr.prev
		if utils.Equals(curr.val, val) {
			list.removeNode(curr)
			removed++
		}
		if removed == count {
			break
		}
		curr = prev
	}
	return removed
}

// Len returns the number of elements in list
func (list *LinkedList) Len() int {
	if list == nil {
		panic("list is nil")
	}
	return list.size
}

// ForEach visits each element in the list
// if the consumer returns false, the loop will be break
func (list *LinkedList) ForEach(consumer func(int, interface{}) bool )  {
	if list == nil {
		panic("list is nil")
	}
	curr := list.first
	i := 0
	for curr != nil {
		canGo := consumer(i, curr.val)
		if !canGo {
			break
		}
		i++
		curr = curr.next
	}
}

// Contains returns whether the given value exist in the list
func (list *LinkedList) Contains(val interface{}) bool {
	contains := false
	list.ForEach(func(i int, currVal interface{}) bool {
		if currVal == val {
			contains = true
			return false
		}
		return true
	})
	return contains
}

// Range returns elements which index within [start, stop)
// 可优化   原文是从头开始找
func (list *LinkedList) Range(start int, stop int) []interface{}  {
	if list == nil {
		panic("list is nil")
	}
	if start < 0 || start >= list.size {
		panic("'start' out of range")
	}
	if stop < start || stop > list.size {
		panic("'stop' out of range")
	}
	curr := list.find(start)
	N := stop - start
	result := make([]interface{}, N)
	i := 0
	for i < N {
		result[i] = curr.val
		curr = curr.next
		i++
	}
	return result
}














